/**
 * @param {number} k
 * @param {number} n
 * @return {number[][]}
 */
var combinationSum3 = function (k, n) {
    if (n < (k * (1 + k) / 2)) return []
    let res = [];
    combinationLevel(k, n, res, [], 1)
    return res
};

function combinationLevel(k, n, res, val, cur) {
    if (val.length > k) return
    let sum = 0
    if (val.length === k) {
        for (let i = 0; i < val.length; i++) {
            sum += val[i]
        }
        if (sum === n) {
            res.push([...val])
            return
        }
    }
    if (sum > n) return

    let max = Math.min(~~((n - sum) / (k - val.length)),9)
    for (let i = cur; i <= max; i++) {
        val.push(i)
        combinationLevel(k, n, res, val, i + 1)
        val.pop()
    }
}